package a_sorting_basic.c_insertion_sort;

import a_sorting_basic.c_insertion_sort.sorting_helper.SortingTestC;
import utils.ArrayGeneric;

/**
 * 2- 插入排序
 * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
 * O（n^2）	    O（n^2）	    O（1）       是
 * 从第二个元素开始，每次和前面的元素比较， 插入到符合排序要求的位置， 类似整理扑克
 * 外层循环次数： 从第二个元素开始遍历
 * 内层循环次数： 每个元素和前面的元素逐个比对和交换，每次确定一个元素的位置
 * 比较时如果发现大于前一个元素时， 由于前面的全都排序好了， 所以可以提前结束当前这一轮的比较
 * 所以平均情况会比选择排序快近一倍时间
 *
 *
 int len = arr.length();
 for (int i = 1; i < len; i++) {
    for (int j = i; j > 0 && arr.get(j - 1).compareTo(arr.get(j)) > 0; j--) {
        arr.swap(j, j - 1);
    }
 }
 *
 *
 * 优化点：减少交换的次数， 直接插入到应该插入的位置
 */
@SuppressWarnings("unchecked")
public class InsertionSortC extends SortingTestC {

    @Override
    public void sort(ArrayGeneric arr) {
        int len = arr.length();
        for (int i = 1; i < len; i++) {
            // 寻找arr.get(i)合适的插入位置
            Comparable e = arr.get(i);
            // j 保存 元素e应该插入的位置
            int j;
            for (j = i; j > 0 && arr.get(j - 1).compareTo(e) > 0; j--) {
                // 如果前一个元素更大， 则前一个元素后移一位
                arr.put(j, arr.get(j - 1));
            }
            // 如果前一个元素更小，再往前的元素也无需判断了（已经有序） 则插入当前位置
            // 虽然第一次比较时就发现前一个元素更小时可以什么也不做
            // if(i == j) continue;
            // 但是判断同样也是有开销的, 因此接近有序的时候效率反而会变低
            // 但是乱序的时候效率会稍稍提高， 但是远不如logN的算法快， 所以这样的改进没有意义
            // 反而这个算法在接近有序的时候效率异常的高 甚至高于NLogN的树形结构
            // 比如系统日志， 理应是按照时间生成的
            // 但是有的时候因为一些错误， 或者生成日志的时间过长导致顺序偶发的不一致
            // 这是采用插入排序就是性能最好的选择！！
            // 最优情况下（完全有序）时间复杂度是N ！！！
            arr.put(j, e);
        }
    }
}
